NC50 链表中的节点每k个一组翻转

https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

1. 如何反转整个链表，比较简单
2. 思考反转链表 前 k 个元素，也比较简单，在 1 的基础上 i < k i++ 即可
3. 反转前 k 个元素之后返回 head，如 head = reverse(p,k) 这样 p 刚好指向反转过的末尾，把反转后的头返回

这样问题简化为一段一段执行第3步

最后一步少于 k 时不反转如何处理？把 3 改一下把反转的次数也返回，head,length = reverse(p,k) 这样 length < k 时再把最后一段反转一次即可，这样可以在反转时计数，防止需要每次计数判断

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode ,  k int ) *ListNode {
    if k == 1 || k == 0 || head == nil {return head}

    var result, pre *ListNode
    cur := head

    for cur != nil {
        tmphead, l := reverse(cur, k)
        // 当翻转的 length 不满 k 时再翻转一遍，还原回去
        if l < k {
            tmphead, _ = reverse(tmphead, k)
        }
        if pre != nil {
            pre.Next = tmphead
        }
        if result == nil {
            result = tmphead
        }
        pre = cur
        cur = cur.Next
    }

    return result
}

// 反转一个链表的前k位，并返回head, 反转之后p刚好指向tail
// 返回反转的长度，如果长度<k,那么说明是最后一次，再反转一次
func reverse(head *ListNode,k int) (*ListNode,int){
    p := head
    tail := head
    var i int
    for i = 0;i<k && p != nil;i++{
        q := p.Next
        p.Next = head
        head = p
        p = q
    }
    tail.Next = p

    return head,i
}